package com.stronger.leetcode.simple;

import java.util.*;

/**
 * @author Created by njy on 2023/6/16
 * 20.有效括号
 */
public class KuoHao20 {


    public static void main(String[] args) {
        boolean valid = isValid("()[]{}");
        System.out.println("valid = " + valid);
    }


    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     * 示例 1：
     * 输入：s = "()"
     * 输出：true
     * 示例2：
     * 输入：s = "()[]{}"
     * 输出：true
     * 示例3：
     * 输入：s = "(]"
     * 输出：false
     * 提示：
     * 1 <= s.length <= 104
     * s 仅由括号 '()[]{}' 组成
     */
    public static boolean isValid(String s) {
        int n=s.length();

        if (n % 2 == 1) {
            return false;
        }
        Map<Character,Character> map=new HashMap<Character, Character>(){{
            put('}','{');
            put(']','[');
            put(')','(');
        }};

        //新建一个栈
        LinkedList<Character> stack=new LinkedList<Character>();

        for (int i = 0; i < n; i++) {
            char c=s.charAt(i);
            //如果C是})]，则判断，否则说明是({[，直接入栈
            if (map.containsKey(c)){
                //stack.peek() 获取栈顶元素
                if(stack.isEmpty() || stack.peek() != map.get(c)){
                    return false;
                }
                //将栈顶移除（先进后厨，栈顶是最接近c的左括号)
                stack.pop();
            }else {
                //说明c是({[，直接入栈
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
